package com.da.javatest.niuke.baodian;

/**
 * @author chenlida
 * @date 2020/10/10 10:50
 * https://www.nowcoder.com/practice/f2976b694c5a4a6497b1d7886894fcdd?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C42MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        return findMagicIndex(A, 0, n - 1);

    }

    public static boolean findMagicIndex(int[] A, int begin, int end) {
        if (begin == end) {
            return false;
        }
        int mid = (begin + end) / 2;
        if (A[mid] > mid) {
            return findMagicIndex(A, begin, mid);
        } else if (A[mid] < mid) {
            return findMagicIndex(A, mid, end);
        } else {
            return true;
        }

    }

    public boolean findMagicIndex2(int[] A, int n) {
        for (int i = 0; i < n; i++) {
            if (A[i] == i) {
                return true;
            }
        }
        return false;
    }
}
